One of the long standing challenges in computing is the detection of deadlocks. A deadlock is a state assumed by a set of entities wherein each entity in the set is waiting for the release of at least one resource owned by another entity in the set. Entities capable of owning a resource are referred to herein as possessory entities. In the context of a database system, for example, possessory entities include processes and transactions. A transaction is an atomic unit of work.
For example, a transaction T1 may seek exclusive ownership of resource R1 and R2. If R1 is available and R2 is currently exclusively owned by another transaction T2, transaction T1 may acquire exclusive ownership of R1 but must wait for R2 to become available. A deadlock will occur if a transaction T2 exclusively owns R2 but seeks ownership of R1, and T2 is suspended to wait for R1 without releasing R2. Because both T1 and T2 are waiting for each other, they are deadlocked.
Computer systems employ a variety of deadlock handling mechanisms (deadlock handlers) that detect deadlocks. Many of deadlock handlers employ the "cycle" technique to detect deadlocks. In the cycle technique, after a process waits a threshold period of time for a resource, a wait-for graph is generated and examined for any cycles. If any cycles are identified, then the deadlock detection mechanism has identified a deadlock.
A wait-for graph is a graph that includes vertices that represent resources ("resource vertices") and vertices that represent possessory entities ("entity vertices "). An arc from an entity vertex to a resource vertex represents that the respective possessory entity represented by the entity vertex is waiting for ownership of the resource. An arc from a resource vertex to an possessory entity node represents that the resource represented by the resource vertex is owned by the possessory entity. A cycle is detected when a chain of arcs leads both to and from the same vertex.
FIG. 1 shows an exemplary wait-for graph 100, which includes entity vertices 111 and 112 and resource vertices 121 and 122. Wait-for graph 100 was generated when a deadlock handler detected that the process represented by entity vertex 111 had waited a threshold period of time for the resource represented by resource vertex 121. Arc 131 represents that the process represented by entity vertex 111 is waiting for the release of the resource represented by resource vertex 121. Arc 132 represents that the resource represented by resource vertex 121 is owned by the process represented by entity vertex 112. Arc 133 represents that the process represented by entity vertex 112 is waiting for the release of the resource represented by resource vertex 122. Arc 134 represents that the resource represented by resource vertex 122 is owned by the resource represented by entity vertex 111.
Arcs 131, 132, 133, and 134 form a loop that both extends from and leads to entity vertex 111, and thus represents a cycle. The processes represented the entity vertices of wait-for graph 100 are therefore potentially deadlocked.
In practice, deadlocks detected through the cycle technique may not actually exist. One reason the cycle technique is not completely accurate is that relationships between possessory entities and resources change while a wait-for graph is being generated. For example, while in the process of generating a wait-for graph, a deadlock handler determines that arc 131 should connect entity vertex 111 to resource vertex 121 because the process represented by entity vertex 111 is waiting for the release of the resource represented by resource vertex 121. Next, the deadlock handler determines that arc 132 should connect resource vertex 121 to entity resource 112 because resource vertex 121 is owned by entity resource 112. The deadlock handler then generates the remainder of wait-for graph 100.
While generating the remainder of wait-for graph 100, the process represented by entity vertex 112 relinquishes ownership of the resource represented by resource vertex 121. Thus upon completion of the wait-for graph, arc 132 in fact represents a nonexistent relationship, and the cycle represented by arcs 131, 132, 133, and 134 represents a nonexistent deadlock.
Because deadlocks identified through the cycle technique may or may not exist, such deadlocks are subjected to further verification before they are treated as deadlocks that exist. The process of verifying the existence of previously identified deadlocks is referred to as "validation". Deadlocks that have been detected but have not yet been subjected to validation are referred to herein as potential deadlocks.
Typically, validation of a potential deadlock involves regenerating a wait-for graph, and determining whether the regenerated wait-for graph contains the same previously identified cycle. If the same cycle exists, the probability that the potential deadlock is an actual deadlock increases greatly, and the potential deadlock is handled as a deadlock. Such handling includes causing one of the possessory entities to relinquish ownership of a resource, thus "breaking the cycle." A potential deadlock that is treated as a real deadlock because its existence has been verified through validation, is referred to herein as a true deadlock.
As shown above, identifying true deadlocks may entail the generation of at least two wait-for graphs. Validating a possible deadlock without performing the amount of work required to generate a second wait-for graph would substantially improve the efficiency of performing validation. It is therefore desirable to provide a method for validation that requires less work than regenerating a wait-for graph, and in particular, requires less work without sacrificing accuracy in validating potential deadlocks.